For a number of years, the evolution of hardware systems followed a rather predictable trend in terms of processing capabilities: the latest generation of processors was significantly faster than the previous, with the rate of speed increase following closely Moore's law. However, higher processor speeds did not always translate to corresponding gains in system performance (with memory speeds and instruction sets often becoming the new performance bottlenecks). This led hardware manufactures to consider alternative architectures in which multiple processing cores are used to execute instructions in parallel. So, whereas the trend before was to increase processor speeds between hardware generations, in the last few years a new trend has emerged where the difference between hardware generations is in the number of cores. Nowadays, it is not uncommon to find eight cores, even in commodity hardware.
Of course, to take advantage of these multiple cores, the parallelization of existing software systems comes at a cost. Existing software systems often cannot be used in a processing environment that employs parallelization and may need to be changed. Indeed, there has been much interest in systems research, including database systems research, on how to harness such parallel processing power.
It is known that the Extensible Markup Language (XML) is the de facto data representation format used today, particularly in database systems. XML is defined by WWW Consortium, “Extensible Markup Language (XML) 1.0 (Fifth Edition),” W3C Recommendation, Nov. 26, 2008, the disclosure of which is incorporated by reference herein. XPath queries, based on the XML Path Language as defined by WWW Consortium, “XML Path Language (XPath) 2.0,” W3C Recommendation, Jan. 23, 2007, the disclosure of which is incorporated by reference herein, are commonly used to query XML data alone or as part of XQuery expressions. Note that XPath 2.0 is a subset of XQuery 1.0 as defined by WWW Consortium, “XML Query Language (XQuery) 1.0,” W3C Recommendation, Jan. 23, 2007, the disclosure of which is incorporated by reference herein Thus, in a multi-core system, effective parallel query evaluation (such as XPath queries) over XML documents is a problem that it would be highly desirable to address and solve.